package com.fanshuai.algorithms.datastructure;

import com.fanshuai.algorithms.datastructure.tree.binarytree.BinaryTree;
import com.fanshuai.tree.Visitor;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //binaryTree1();
        //buildTree2();

        //getMaxPath();
        //theSameTree();

        //commonAncestor();
        //validBST();
        pathSum();
    }

    private static Integer[] a1 = {13, 31, 21, 12, null, 25, 45,
            61, null, null, null, 32, 27, null, 18};

    private static Integer[] a2 = {2, 1, 3, 5, 4, null, 7,
            9, null, 0, 11, null, null, 8, 12};

    /**
     * 1 build from BFS
     * 3 in order visit
     */
    private static void binaryTree1() {
        BinaryTree.Node node = BinaryTree.buildTreeFromBFS(a1);
        visitTree(node);

        node = BinaryTree.buildTreeFromBFS(a2);
        visitTree(node);
    }

    private static void visitTree(BinaryTree.Node node) {
        List<Integer> list = new ArrayList<>();
        BinaryTree.BFS(node, new Visitor() {
            @Override
            public void visit(int value) {
                list.add(value);
            }
        });
        System.out.println(list);

        list.clear();
        BinaryTree.inOrder(node, new Visitor() {
            @Override
            public void visit(int value) {
                list.add(value);
            }
        });
        System.out.println(list);
    }

    /**
     * 4 build from in-order and pre-order
     */
    private static void buildTree2() {
        int[] pre = {2, 1, 5, 9, 4, 0, 11, 3, 7, 8};
        int[] in = {9, 5, 1, 0, 4, 11, 2, 3, 8, 7};

        BinaryTree.Node node = BinaryTree.buildTree(pre, in);
        visitTree(node);
    }

    /**
     * 5 get max path 1-3
     */
    private static void getMaxPath() {
        BinaryTree.Node node = BinaryTree.buildTreeFromBFS(a1);
        int max = BinaryTree.getMaxPath1(node);
        System.out.println(max);

        max = BinaryTree.getMaxPath2(node);
        System.out.println(max);

        List<Integer> maxPath = BinaryTree.getMaxPath3(node);
        System.out.println(maxPath);

        BinaryTree.Node node2 = BinaryTree.buildTreeFromBFS(a2);
        int max2 = BinaryTree.getMaxPath1(node2);
        System.out.println(max2);

        max2 = BinaryTree.getMaxPath2(node2);
        System.out.println(max2);

        List<Integer> maxPath2 = BinaryTree.getMaxPath3(node2);
        System.out.println(maxPath2);
    }

    /**
     * 2 find node
     * 6 find common ancestor
     */
    private static void commonAncestor() {
        BinaryTree.Node node = BinaryTree.buildTreeFromBFS(a2);

        int[] c1 = {9, 0, 11};
        int[] c2 = {9, 5, 4};
        int[] c3 = {11, 7, 8};
        int[] c4 = {0, 11, 4};

        commonAncestor0(node, c1);
        commonAncestor0(node, c2);
        commonAncestor0(node, c3);
        commonAncestor0(node, c4);
    }

    private static void commonAncestor0(BinaryTree.Node node, int[] c) {
        BinaryTree.Node[] nodes = new BinaryTree.Node[c.length];
        for (int i = 0; i < c.length; i++) {
            nodes[i] = BinaryTree.findNode(node, c[i]);
        }

        BinaryTree.Node commonNode = BinaryTree.commonAncestor(node, nodes);
        System.out.println("common ancestor=" + (null == commonNode ? null : commonNode.value));
    }

    /**
     * 7 the same binary tree
     */
    private static void theSameTree() {
        BinaryTree.Node node = BinaryTree.buildTreeFromBFS(a1);
        BinaryTree.Node node2 = BinaryTree.buildTreeFromBFS(a2);
        BinaryTree.Node node3 = BinaryTree.buildTreeFromBFS(a1);

        System.out.println(BinaryTree.isSame(node, node2));
        System.out.println(BinaryTree.isSame(node, node3));
    }

    private static void validBST() {
        Integer[] tree = {1, 2, 3, 4, 5, null, null, 8, 9, 10};
        Integer[] tree2 = {13, 10, 20, 8, null, 15, null, 6, 9, null, 16};

        BinaryTree.Node node = BinaryTree.buildTreeFromBFS(tree);
        BinaryTree.Node node2 = BinaryTree.buildTreeFromBFS(tree2);

        System.out.println(BinaryTree.isValidBST(node));
        System.out.println(BinaryTree.isValidBST(node2));
    }

    private static void pathSum() {
        Integer[] tree = {10,5,-3,3,2,null,11,3,-2,null,1};

        BinaryTree.Node root = BinaryTree.buildTreeFromBFS(tree);
        System.out.println(BinaryTree.pathSum(root, 8));
        System.out.println(BinaryTree.pathSum2(root, 8));
    }
}
